package liujia.bt.util
{
	
	public class ArrayUtils
	{
		
		///////////////数组增删改查工具，从superArray移植过来/////////////
		/**
		 * 插入指定对象
		 * example: ArrayUtils.setElement(arr, myObject, {id:3})
		 * 遍历数组中的元素，找到id==3的元素，更新为myObject 并返回true, 如果找不到，那么push这个myObject 并返回false
		 * 如果找到id==3的元素是多个，那么只有第一个id==3的元素的引用都指向myObject
		 * return true 覆盖这个找到的元素  false 使用push方法新增这个元素
		 * */
		public static function setElement(arr:Array, element:*, if_factor:Object=null):Boolean{
			if(if_factor == null){ 
				arr.push(element);
				return false;
			}
			for each(var o:Object in arr){
				if( isTheOne(o, if_factor) ){
					arr[arr.indexOf(o)] = element;
					return true;
				}
			}
			
			arr.push(element);
			return false;
		}
		
		/**
		 * 是否包含元素
		 * example: ArrayUtils.containElement(arr, {id:3, name:"liu"})
		 * 遍历数组中的元素，找到id==3且name=="liu"的元素，返回true, 否则返回false
		 * */
		public static function containElement(arr:Array, if_factor:Object):Boolean {
			var o:* = getElement(arr, if_factor);
			return (o!=null);
		}
		
		/**
		 * 取出符合条件的对象
		 * example: ArrayUtils.getElement(arr, {id:3, name:"liu"})
		 * 遍历数组中的元素，找到id==3且name=="liu"的元素，返回这个元素
		 * 如果找到id==3的元素是多个，那么只返回第一个
		 * */
		public static function getElement(arr:Array, if_factor:Object):*{
			for each(var o:Object in arr){
				if( isTheOne(o, if_factor) ){
					return o;
				}
			}
			return null;
		}
		
		/**
		 * 取出符合条件的所有对象
		 * example: ArrayUtils.getAllElements(arr, {id:3})
		 * 遍历数组中的元素，找到所有id==3的元素，生成一个数组返回
		 * 若找不到，返回[]
		 * */
		public static function getAllElements(arr:Array, if_factor:Object):Array{
			var resaultArr:Array = [];
			for each(var o:Object in arr){
				if( isTheOne(o, if_factor) ){
					resaultArr.push(o);
				}
			}
			return resaultArr;
		}
		
		/**
		 * 取出不符合条件的所有对象
		 * example: ArrayUtils.getAllElementsExcept(arr, {type:3})
		 * 遍历数组中的元素，找到所有type!=3的元素，生成一个数组返回
		 * 若找不到，返回[]
		 * */
		public static function getAllElementsExcept(arr:Array, if_factor:Object):Array{
			var resaultArr:Array = arr.concat();
			for each(var o:Object in arr){
				if( isTheOne(o, if_factor) ){
					resaultArr.splice(resaultArr.indexOf(o), 1);
				}
			}
			return resaultArr;
		}
		
		/**
		 * 删除符合条件的对象
		 * example: ArrayUtils.delElement(arr, {id:3, name:"liu"})
		 * 遍历数组中的元素，找到id==3且name=="liu"的元素，删除这个元素 并返回这个元素
		 * 如果找到id==3的元素是多个，删除第一个 并返回
		 * */
		public static function delElement(arr:Array, if_factor:Object):*{
			for(var i:int=0;i<arr.length;i++){
				var o:Object = arr[i];
				if( isTheOne(o, if_factor) ){
					arr.splice(i, 1);
					i--;
					return o;
				}
			}
			return null;
		}
		
		/**
		 * 删除符合条件的对象
		 * example: ArrayUtils.delElement(arr, {type:"A"})
		 * 遍历数组中的元素，找到所有type=="A"的元素，删除这些元素 并用数组返回这些元素
		 * 如果找到id==3的元素是多个，那么全部删除
		 * */
		public static function delAllElements(arr:Array, if_factor:Object):Array{
			var resaultArr:Array = [];
			for(var i:int=0;i<arr.length;i++){
				var o:Object = arr[i];
				if( isTheOne(o, if_factor) ){
					arr.splice(i, 1);
					i--;
					resaultArr.push(o);
				}
			}
			return resaultArr;
		}
		
		/**
		 * 找到符合条件元素，更新它们，默认更新所有元素
		 * example: ArrayUtils.updateElements(arr, {height:180}, {type:"A"})
		 * 遍历数组中的元素，找到所有type=="A"的元素, 把元素的height属性设置为180
		 * 如果if_factor==null，则把所有元素的height属性设置为180
		 */		
		public static function updateAllElements(arr:Array, attribute:Object, if_factor:Object=null):void {
			var o:Object = null;
			if(if_factor != null){
				for each(o in arr){
					if ( isTheOne(o, if_factor) ) {
						assign(o, attribute);
					}
				}
			}else{
				for each(o in arr){
					assign(o, attribute);
				}
			}
		}
		
		/**
		 *把 attribute的属性-属性值 赋给 o
		 * @param o
		 * @param attribute
		 * 
		 */		
		private static function assign(o:Object, attribute:Object):void {
			for(var attribute_keyname:String in attribute){
				o[attribute_keyname] = attribute[attribute_keyname];
			}
		}
		
		/**
		 * 该对象是否符合条件表达式 
		 * @param obj 对象
		 * @param if_factor 条件表达式 JSON格式
		 * 
		 */		
		private static function isTheOne(o:*, if_factor:Object):Boolean {
			var isTheOne:Boolean = false;
			for(var keyname:String in if_factor){
				if(o[keyname] == if_factor[keyname]){
					isTheOne = true;
				}else{
					isTheOne = false;
					break;
				}
			}
			return isTheOne;
		}
		
		
		
		/**
		 * 从数组里移除一个对象，使用splice，有序的，如果有多个索引引用到该对象，只移除第一个索引
		 * @param arr 数组
		 * @param obj 对象
		 * @return 该元素在数组中得索引
		 * 
		 */		
		public static function removeFromArray(arr:Array, obj:Object):int{
			var i:int = arr.indexOf(obj);
			if (i != -1)
				arr.splice(i, 1);
			return i;
		}
		
		/**
		 * 从数组里移除一个对象，使用pop，无序的，效率比splice高，如果有多个索引引用到该对象，只移除第一个索引
		 * @param arr 数组
		 * @param obj 对象
		 * @return 该元素在数组中得索引
		 * 
		 */		
		public static function removeUsePop(arr:Array, obj:Object):int{
			var i:int = arr.indexOf(obj);
			if (i != -1) {
				arr[i] = arr[arr.length-1];
				arr.pop();
			}
			return i;
		}
		
		/**
		 * 从数组里移除对象，使用splice，有序的，如果有多个索引引用到该对象，移除全部索引
		 * @param arr 数组
		 * @param obj 对象
		 * 
		 */		
		public static function removeAllFromArray(arr:Array, obj:Object):void{
			while ( removeFromArray(arr, obj) != -1) { }
		}
		
		/**
		 * 从数组里移除对象，使用pop，无序的，效率比splice高，如果有多个索引引用到该对象，移除全部索引
		 * @param arr 数组
		 * @param obj 对象
		 * 
		 */		
		public static function removeAllUsePop(arr:Array, obj:Object):void{
			while ( removeUsePop(arr, obj) != -1) { }
		}
		
		/**
		 * 移除数组中某个索引之后的所有索引，其实就是array.splice(index + 1);这个方法有点多余 
		 * @param array 数组
		 * @param index 索引
		 * 
		 */		
		public static function removeAllBehindSomeIndex(array:Array , index:int):void{
			if(index <= 0){
				array.splice(0);
			}
			else {
				array.splice(index + 1);
			}
		}
		
		/**
		 * 移除数组中的多个对象
		 * @param srcArr 数组
		 * @param delArr 要移除的对象
		 * 
		 */		
		public static function batchDelete(srcArr:Array,delArr:Array):void{
			for each(var item:* in delArr){
				removeFromArray(srcArr,item);
			}
		}
		
		/**
		 * 把对象加进数组，可避免重复加入
		 * @param arr 数组
		 * @param item 对象 
		 * 
		 */		
		public static function pustItemOnce(arr:Array,item:*):void{
			var index:int = arr.indexOf(item);
			if(index == -1){
				arr.push(item);
			}
		}
		
		/**
		 * 浅克隆数组，其实就是 arr.concat(); 这个方法比较多余 
		 * @param arr 数组
		 * @return 
		 * 
		 */		
		public static function cloneArray(arr:Array):Array{
			return arr.concat();
		}
		
		/**
		 * 深克隆数组，调用数组里每个对象的clone()方法，如果对象没有clone()方法，必然克隆失败
		 * @param a 数组
		 * @return 
		 * 
		 */		
		public static function deepClone(a:Array):Array {
			var r:Array = new Array();
			for each (var obj:Object in a) {
				if (obj.hasOwnProperty("clone")) {
					obj = obj.clone();
				}
				r.push(obj);
			}
			return r;
		}
		
		/**
		 *在索引区间浅克隆数组,索引区间包括start和end索引 
		 * @param dst 克隆出来的新数组
		 * @param src 源数组
		 * @param start 开始的索引
		 * @param end 结束的索引
		 * @return 克隆是否成功
		 * 
		 */		
		public static function copyArrayByRange(dst:Array, src:Array, start:int, end:int):Boolean {
			if (dst == null || src == null)
				return false;
			
			var l:int = src.length;
			if (l == 0 || l <= end)
				return false;
			
			dst.splice(0);
			for (var i:int = start; i <= end; ++i) {
				dst.push(src[i]);
			}
			return true;
		}
		
		/**
		 * 把数组的索引混淆 
		 * @param array 数组
		 * 
		 */		
		public static function mixArray(array:Array):void{
			array.sort(function(n1:*, n2:*):Number{
				var r:Number = Math.random()*1;
				return r>0.5?1:-1;
			});
		}
		
		/**
		 * 把数组的两个索引互相交换位置 
		 * @param array 数组
		 * @param i 第一个索引
		 * @param j 第二个索引
		 * 
		 */		
		public static function swap(array:Array, i:int, j:int):void {
			var t:Object = array[i];
			array[i] = array[j];
			array[j] = t;
		}
		
		/**
		 * 冒泡排序
		 * @param array 数组
		 * @param fnCompare 格式 func(obj0:*, obj1:*):Boolean
		 * 
		 */		
		public static function bubbleSort(array:Array, fnCompare:Function):void {
			var c:int = array.length - 1;
			for (var i:int = 0; i < c; ++i) {
				var bSwapped:Boolean = false;
				for (var j:int = 0; j < c - i; ++j) {
					if (fnCompare(array[j + 1], array[j])) {
						swap(array, j, j + 1);
						bSwapped = true;
					}
				}
				if (!bSwapped) {
					break;
				}
			}
		}
		
		/**
		 * 快速排序 
		 * @param array 数组
		 * @param fnCompare 格式 func(obj0:*, obj1:*):Boolean
		 * 
		 */		
		public static function quickSort(array:Array, fnCompare:Function):void {
			doQuickSort(array, fnCompare, 0, array.length - 1);
		}
		
		private static function doQuickSort(array:Array, fnCompare:Function, bottom:int, top:int):void {
			if (top > bottom) {
				var piv:int = bottom;
				var k:int = bottom + 1;
				var r:int = top;
				var pivObj:Object = array[piv];
				while (k != r /*k < r*/) {
					if (fnCompare(array[k], pivObj)) {
						++k;
					}
					else {
						swap(array, k, r--);
					}
				}
				if (fnCompare(array[k], pivObj)) {
					swap(array, k, bottom);
					doQuickSort(array, fnCompare, bottom, k - 1);
					doQuickSort(array, fnCompare, r + 1, top);
				}
				else {
					if (top - bottom > 1) {
						--k;
						swap(array, k, bottom);
						doQuickSort(array, fnCompare, bottom, k - 1);
						doQuickSort(array, fnCompare, k + 1, top);
					}
				}
			}
		}
		
		/**
		 * 选择排序 
		 * @param array 数组
		 * @param fnCompare 格式 func(obj0:*, obj1:*):Boolean
		 * 
		 */		
		public static function selectSort(array:Array, fnCompare:Function):void {
			var l:int = array.length;
			for (var i:int = 1; i < l; ++i) {
				var iMin:int = i - 1;
				var minCh:Object = array[iMin];
				for (var j:int = i; j < l; ++j) {
					var ch:Object = array[j];
					if (fnCompare(ch, minCh)) {
						iMin = j;
						minCh = ch;
					}
				}
				if (iMin != (i - 1)) {
					swap(array, iMin, i - 1);
				}
			}
		}
		
		/**
		 * 哈希排序 
		 * @param array 数组
		 * @param fnCompare 格式 func(obj0:*, obj1:*):Boolean
		 * 
		 */		
		public static function heapSort(array:Array, fnCompare:Function):void {
			for (var i:int = array.length - 1; i > 0; --i) {
				heapTree(array, fnCompare, i, i);
			}
		}
		
		private static function heapTree(array:Array, fnCompare:Function, iRootIndex:int, iTopIndex:int):void {
			if (iRootIndex > iTopIndex) {
				return;
			}
			
			var iLeftIndex:int = 0;
			var iRightIndex:int = 1;
			if (iRootIndex < iTopIndex) {
				iLeftIndex = (iRootIndex + 1) * 2;
				iRightIndex = iLeftIndex + 1;
			}
			
			if (iLeftIndex < iTopIndex) {
				var chRoot:Object = array[iRootIndex];
				var chLeft:Object = array[iLeftIndex];
				if (iRightIndex < iTopIndex) {
					var chRight:Object = array[iRightIndex];
					if (fnCompare(chRight, chLeft)) {
						if (fnCompare(chRoot, chLeft)) {
							swap(array, iLeftIndex, iRootIndex);
						}
					}
					else {
						if (fnCompare(chRoot, chRight)) {
							swap(array, iRightIndex, iRootIndex);
						}
					}
					
					heapTree(array, fnCompare, iLeftIndex, iTopIndex);
					heapTree(array, fnCompare, iRightIndex, iTopIndex);
					
					chRoot = array[iRootIndex];
					chLeft = array[iLeftIndex];
					chRight = array[iRightIndex];
					if (fnCompare(chRight, chLeft)) {
						if (fnCompare(chRoot, chLeft)) {
							swap(array, iLeftIndex, iRootIndex);
						}
					}
					else {
						if (fnCompare(chRoot, chRight)) {
							swap(array, iRightIndex, iRootIndex);
						}
					}
				}
				else {
					if (fnCompare(chRoot, chLeft)) {
						swap(array, iLeftIndex, iRootIndex);
					}
				}
			}
			else {
				
			}
		}
	}
	
}